package com.c2b.algorithm.leetcode.base;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href='https://leetcode.cn/problems/make-array-zero-by-subtracting-equal-amounts/'>使数组中所有元素都等于零(Make Array Zero by Subtracting Equal Amounts)</a>
 * <p>
 * 给你一个非负整数数组 nums 。在一步操作中，你必须：
 *     <ul>
 *         <li>选出一个正整数 x ，x 需要小于或等于 nums 中 最小 的 非零 元素。</li>
 *         <li>nums 中的每个正整数都减去 x。</li>
 *     </ul>
 * </p>
 * <p>返回使 nums 中所有元素都等于 0 需要的 最少 操作数。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [1,5,0,3,5]
 *      输出：3
 *      解释：
 *          第一步操作：选出 x = 1 ，之后 nums = [0,4,0,2,4] 。
 *          第二步操作：选出 x = 2 ，之后 nums = [0,2,0,0,2] 。
 *          第三步操作：选出 x = 2 ，之后 nums = [0,0,0,0,0] 。
 *
 * 示例 2：
 *      输入：nums = [0]
 *      输出：0
 *      解释：nums 中的每个元素都已经是 0 ，所以不需要执行任何操作。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>1 <= nums.length <= 100</li>
 *      <li>0 <= nums[i] <= 100</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/22 17:03
 */
public class LC2357MakeArrayZeroBySubtractingEqualAmounts_S {

    static class Solution {

        public int minimumOperations(int[] nums) {
            boolean[] exists = new boolean[101];
            exists[0] = true;
            int ans = 0;
            for (int num : nums) {
                if (!exists[num]) {
                    ++ans;
                    exists[num] = true;
                }
            }
            return ans;
        }

        /**
         * 由于每次操作都将数组中的所有非零元素减少一个相同的值，因此数组中的相等元素减少到 0 的操作数相等，数组中的不相等元素减少到 0 的操作数不相等。
         */
        public int minimumOperations2(int[] nums) {
            Set<Integer> set = new HashSet<Integer>();
            for (int num : nums) {
                if (num > 0) {
                    set.add(num);
                }
            }
            return set.size();
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minimumOperations(new int[]{1, 5, 0, 3, 5}));
        System.out.println(solution.minimumOperations(new int[]{0}));
    }
}
